package com.cty._05_Ability._56_02_NumberAppearOnce;

/**
 * @Auther: cty
 * @Date: 2020/7/22 20:38
 * @Description: 面试题56（二）：数组中唯一只出现一次的数字
 * 题目：在一个数组中除了一个数字只出现一次之外，其他数字都出现了三次。请
 * 找出那个吃出现一次的数字。
 * @version: 1.0
 */
public class NumberAppearOnce {

    public static int numberAppearOnce(int[] array) throws Exception {
        if(array==null || array.length<1)
            throw new Exception("Invalid input");

        int[] table = new int[32];
        for(int i=0; i<array.length; i++){
            int bitMask = 1;
            for(int j=31; j>=0; j--) {
                int bit = array[i] & bitMask;
                if(bit != 0)
                    table[j] += 1;
                bitMask = bitMask << 1;
            }  // end for 0-31
        }  // end for 0-array.length

        int result = 0;
        for(int i=0; i<32; i++){
            result = result << 1;
            result += (table[i] % 3);
        }  // end for
        return result;
    }  // end numberAppearOnce()

}  // end class
